Some systems queue data elements and sort the queue, such as in the case of queuing data packets for processing in a desired order with real-time or non-real-time communications. A basic queue sorting algorithm includes maintaining a sorted list of elements. New elements are inserted in-order by scanning from the head of the queue and placing the new element in the appropriate (sorted) position within the list. Elements are removed from the head of the list to process them in sequence. Such algorithm may be inefficient when elements commonly are inserted in the middle of the list (i.e. not at the head), which is the case when reordering the elements.
A more efficient algorithm includes implementing a sorted list as an ordered binary tree with the root of the tree being the next available element in the sequence. This form of binary tree is also referred to as a “min-heap”. This solution improves on the search performance required to find the insertion point by reducing the search time to O(1) but still uses several nodes of the tree to be visited and possibly swapped. Insertion overhead can still be inefficient as the common case of insertion usually involves a rebalance of the tree. Thus, while such algorithm may be well-suited for efficiently sorting a general purpose data set, it is generally not suitable for real-time packet processing.
A more general approach than using an ordered queue is to simply block the processing of a current element at a critical section that uses ordered processing. Such mechanism stalls the current handling of the element to wait for an element that must be processed before the current one. This is a simple algorithm, but causes significant degradation of performance since the stalling of other processing engines in a system can erode performance throughput.
The approaches above do not offer a sorting or ordering algorithm to efficiently order data packets in real-time or near real-time as they are passed through a multicore parallel processing computing system.